#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
// 15.三数之和
// 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
// 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
// 请你返回所有和为 0 且不重复的三元组。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = nums.size();    // 数组元素个数
        if(n < 3)
            return ans;
        // 先对数组进行排序
        sort(nums.begin(),nums.end());

        for(int i = 0; i < n-2; i++) {    // 枚举第1个数
            if(nums[i] > 0)
                break;  // 剪枝
            if(i > 0 && nums[i] == nums[i-1])  // 第1个数去重：与前一个数相同，直接过滤，可以提升性能
                continue;
            // 开始双指针扫描
            int l = i+1, r = n-1;   // 双指针
            while(l < r) {
                int res = nums[i] + nums[l] + nums[r];  // 三数之和
                if(res == 0) {
                    ans.push_back({nums[i],nums[l],nums[r]});
                    l++,r--;    // 两个指针往中间移动
                    // 指针移动之后，要去重
                    while(l < r && nums[l] == nums[l-1]) l++;   // 左侧去重，第2个元素去重
                    while(l < r && nums[r] == nums[r+1]) r--;   // 右侧去重，第3个元素去重
                } else if(res < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return ans;
    }
};

int main() {
    vector<int> nums1 = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> res = Solution().threeSum(nums1);
    for( int i = 0 ; i < res.size() ; i ++ ){
        for( int j = 0 ; j < res[i].size() ; j ++ )
            cout<<res[i][j]<<" ";
        cout<<endl;
    }

    return 0;
}
